package 每日一题;

/**
 * @description: 小白白每日一题
 * @author: 小白白
 * @create: 2021-05-16
 **/

public class No421数组中两个数的最大异或值 {

    /**
     * 给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。
     * 进阶：你可以在 O(n) 的时间解决这个问题吗？
     *
     * 示例 1：
     * 输入：nums = [3,10,5,25,2,8]
     * 输出：28
     * 解释：最大运算结果是 5 XOR 25 = 28.
     * 示例 2：
     * 输入：nums = [0]
     * 输出：0
     * 示例 3：
     * 输入：nums = [2,4]
     * 输出：6
     * 示例 4：
     * 输入：nums = [8,10,2]
     * 输出：10
     * 示例 5：
     * 输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
     * 输出：127
     *  
     *
     * 提示：
     * 1 <= nums.length <= 2 * 104
     * 0 <= nums[i] <= 231 - 1
     */

    private class Trie{

        public int val;
        //左0
        public Trie left;
        //右1
        public Trie right;
        public Trie(int val) {
            this.val = val;
        }
    }

    public int findMaximumXOR(int[] nums) {

        /**
         * 每构建一次后就去用当前的数去遍历一下当前的树
         */
        Trie root=new Trie(-1);
        int result=0;
        int maxDeep=0;
        String[] unsignedStringArr=new String[nums.length];

        for (int i = 0; i < nums.length; i++) {
            unsignedStringArr[i]=Integer.toBinaryString(nums[i]);
            maxDeep=Math.max(maxDeep,unsignedStringArr[i].length());
        }

        for (int i = 0; i < nums.length; i++) {

            if(unsignedStringArr[i].length()<maxDeep){
                StringBuilder unsignedString = new StringBuilder(unsignedStringArr[i]);
                if(unsignedString.length()<maxDeep){
                    for (int j = 0; j < maxDeep - unsignedStringArr[i].length(); j++) {
                        unsignedString.insert(0, "0");
                    }
                }
                unsignedStringArr[i]=unsignedString.toString();
            }
        }

        for (String value : unsignedStringArr) {
            //二进制数字
            char[] arr = value.toCharArray();
            Trie cur = root;
            for (char c : arr) {
                int itemNum = c - '0';
                if (itemNum == 0) {

                    if (cur.left == null) {
                        cur.left = new Trie(0);
                    }
                    cur = cur.left;

                } else {

                    if (cur.right == null) {
                        cur.right = new Trie(1);
                    }
                    cur = cur.right;

                }
            }
        }

        for (String s : unsignedStringArr) {
            char[] arr = s.toCharArray();
            Trie cur = root;
            StringBuilder sb = new StringBuilder();
            //放置完当前的数字了,可以开始用当前数字遍历此前缀树了
            for (int j = 0; j < arr.length; j++) {
                int itemNum = arr[j] - '0';

                if (cur.left == null && cur.right == null) {
                    //到底了,应该把剩余的加上
                    for (int k = j; k < arr.length; k++) {
                        sb.append(arr[k]);
                    }
                    break;
                }

                if (itemNum == 0) {

                    if (cur.right != null) {
                        //去右1比较好
                        cur = cur.right;
                        sb.append(1);
                    } else {
                        //没有右1,那就求次去左0了
                        cur = cur.left;
                        sb.append(0);
                    }

                } else {

                    if (cur.left != null) {
                        //去左0比较好
                        cur = cur.left;
                        sb.append(1);
                    } else {
                        //没有左0,那就求次去右1了
                        cur = cur.right;
                        sb.append(0);
                    }

                }
            }
            //比较
            result = Math.max(result, Integer.parseInt(sb.toString(), 2));
        }
        return result;

    }

    public static void main(String[] args) {
        No421数组中两个数的最大异或值 n=new No421数组中两个数的最大异或值();
        int[] arr={14,70,53,83,49,91,36,80,92,51,66,70};
        int result = n.findMaximumXOR(arr);
        System.out.println(result);

    }

}
